package com.xiyou.week01.qeque;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 84. 柱状图中最大的矩形
 *
 * @ClassName：LeetCode84
 * @Author：西柚
 * @Date：2022/1/4 5:47 下午
 * @Versiion：1.0
 */
public class LargestRectangleArea {

    /**
     * 输入：heights = [2,1,5,6,2,3]
     * 输出：10
     * 解释：最大的矩形为图中红色区域，面积为 10
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }

        int res = 0;
        for (int i = 0; i < len; i++) {
            // 找到左边最后1个大于等于heights[i]的下标
            int left = i;
            int curHeight = heights[i];
            while (left > 0 && heights[left - 1] >= curHeight) {
                left--;
            }

            // 找到右边最后1个大于等于heights[i]的下标
            int right = i;
            while (right < len - 1 && heights[right + 1] >= curHeight) {
                right++;
            }

            int width = right - left + 1;
            res = Math.max(res, width * curHeight);
        }

        return res;
    }

    /**
     * 输入：heights = [2,1,5,6,2,3]
     * 输出：10
     * 解释：最大的矩形为图中红色区域，面积为 10
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea2(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return heights[0];
        }

        int res = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>(len);
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                while (!stack.isEmpty() && heights[stack.peekLast()] == curHeight) {
                    stack.pollLast();
                }

                int curWidth;
                if (stack.isEmpty()) {
                    curWidth = i;
                } else {
                    curWidth = i - stack.peekLast() - 1;
                }

                res = Math.max(res, curWidth * curHeight);
            }
            stack.addLast(i);
        }

        while (!stack.isEmpty()) {
            int curHeight = heights[stack.pollLast()];
            while (!stack.isEmpty() && heights[stack.peekLast()] == curHeight) {
                stack.pollLast();
            }

            int curWidth;
            if (stack.isEmpty()) {
                curWidth = len;
            } else {
                curWidth = len - stack.peekLast() - 1;
            }

            res = Math.max(res, curWidth * curHeight);
        }

        return res;
    }


    /**
     * 输入：heights = [2,1,5,6,2,3]
     * 输出：10
     * 解释：最大的矩形为图中红色区域，面积为 10
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea3(int[] heights) {
        // 新数组，长度为原数组长度+1
        int[] b = new int[heights.length + 1];
        // 将原数组内容复制新数组b
        System.arraycopy(heights, 0, b, 0, heights.length);
        // b数组新增元素，保证最后栈被弹空
        b[heights.length] = 0;

        int ans = 0;
        Stack<Rect> s = new Stack<Rect>();
        for (int height : b) {
            // 累计宽度
            int accumulatedWidth = 0;
            // 栈顶（之前）高度 >= 当前高度，单调性破坏，确定了栈顶高度的扩展范围，需要删除栈顶
            while (!s.isEmpty() && s.peek().height >= height) {
                accumulatedWidth += s.peek().width;
                ans = Math.max(ans, s.peek().height * accumulatedWidth);
                s.pop();
            }
            s.push(new Rect(accumulatedWidth + 1, height));
        }
        return ans;
    }

    static class Rect {
        int width;
        int height;

        Rect(int width, int height) {
            this.width = width;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
//        int[] heights = {2, 4};
//        System.out.println(largestRectangleArea(heights));
//        System.out.println(largestRectangleArea2(heights));
        System.out.println(largestRectangleArea3(heights));
    }
}
